package tree.searchTree.prefixTree;

import java.util.Arrays;
import java.util.List;

/**
 * 功能描述: 26个字母的前缀树
 * 2024/05/25
 * <p>
 * ZhangYi
 */
public class PrefixTrie_26Utils {

    public static class Node{
        private int pass;
        private int end;

        private Node[] next;

        public Node() {
            this.pass = 0;
            this.end = 0;
            this.next = new Node[26];
        }
    }

    public static class Trie26{
        // 初始化根节点, 不存储任何的字符信息,只记录了pass信息
        private Node root = new Node();

        /**
         * 功能描述: 插入一个单词
         *
         * @param word 字
         */
        public void insert(String word){
            if (word == null){
                return;
            }
            Node cur = root;
            cur.pass++;

            char[] charArray = word.toCharArray();
            int index = 0;


            for (int i = 0; i < charArray.length; i++) {
                index = charArray[i]-'a';
                if (cur.next[index] == null ){
                    cur.next[index] = new Node();
                }
                cur.next[index].pass++;
                cur = cur.next[index];
            }

            cur.end++;
        }


        /**
         * 功能描述: 查询单词
         *
         * @param word 字
         * @return int
         */
        public int search(String word){
            if (word == null){
                return 0;
            }

            Node cur = root;
            int index = 0;

            char[] charArray = word.toCharArray();

            for (int i = 0; i < charArray.length; i++) {
                index = charArray[i]-'a';
                if (cur.next[index] == null){
                    return 0;
                }
                cur = cur.next[index];
            }


            return cur.end;
        }


        /**
         * 功能描述: 前缀查询
         *
         * @param prefix 前缀
         * @return int
         */
        public int preFind(String prefix){
            if (prefix == null){
                return 0;
            }

            Node cur = root;
            int index = 0;

            char[] charArray = prefix.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
                index = charArray[i]-'a';
                if (cur.next[index] == null){
                    return 0;
                }

                cur = cur.next[index];
            }
            return cur.pass;
        }


        /**
         * 功能描述: 删除一个单词
         *
         * @param word 字
         */
        public void delete(String word){
            if (word == null){
                return;
            }

            Node cur = root;
            int index = 0;

            char[] charArray = word.toCharArray();

            for (int i = 0; i < charArray.length; i++) {
                index = charArray[i]-'a';

                if ((--cur.next[index].pass ) == 0){
                    cur.next[index]= null;
                }

                cur = cur.next[index];
            }
        }
    }

    public static void main(String[] args) {
        Trie26 trie26 = new Trie26();
        List<String> words = Arrays.asList("abc",
                                           "abd",
                                           "abf",
                                           "abg",
                                           "ab",
                                           "bdf",
                                           "dfa",
                                           "dfd"
                                           );

        for (String word : words) {
            trie26.insert(word);
        }

        //System.out.println(1);
        String preFindStr = "ab";
        System.out.println(String.format("以 %s 为前缀出现的次数为 %d",preFindStr,trie26.preFind(preFindStr)));

        preFindStr ="df";
        System.out.println(String.format("以 %s 为前缀出现的次数为 %d",preFindStr,trie26.preFind(preFindStr)));

        preFindStr ="b";
        System.out.println(String.format("以 %s 为前缀出现的次数为 %d",preFindStr,trie26.preFind(preFindStr)));

        preFindStr ="c";
        System.out.println(String.format("以 %s 为前缀出现的次数为 %d",preFindStr,trie26.preFind(preFindStr)));
    }
}
